#include <memory>
#include <unordered_map>

struct RandomListNode {
    int label;
    RandomListNode *next, *random;
    RandomListNode(int x) : label(x), next(nullptr),random(nullptr) {}
};

class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
		std::unordered_map<RandomListNode*, RandomListNode*> oldNewMap;
		std::unordered_map<RandomListNode*, RandomListNode*> newOldRandomMap;
		auto header = std::unique_ptr<RandomListNode>(new RandomListNode(0));
		auto newHead = header.get();
		while (head) {
			auto tmp = new RandomListNode(head->label);
			oldNewMap.emplace(head, tmp);
			newOldRandomMap.emplace(tmp, head->random);
			newHead->next = tmp;
			head = head->next;
			newHead = newHead->next;
		}
		newHead = header->next;
		while (newHead) {
			auto oldRandom = newOldRandomMap[newHead];
			if (oldRandom) {
				newHead->random = oldNewMap[oldRandom];
			}
			newHead = newHead->next;
		}
		return header->next;
    }
};